#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include "dsexceptions.h"
#include <algorithm>
using namespace std;       

/// @brief BinarySearchTree的Comparable模板类;
/// @tparam Comparable BinarySearchTree的类型;
template <typename Comparable>
class BinarySearchTree
{
  public:
    /// @brief 默认BinarySearchTree构造函数;
    BinarySearchTree( ) : root{ nullptr }
    {
    }

    /// @brief 有左值传入的BinarySearchTree构造函数;
    /// @param rhs 传入的BinarySearchTree左值引用rhs;
    BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
    {
        root = clone( rhs.root );
    }

    /// @brief 有右值传入的BinarySearchTree构造函数;
    /// @param rhs 传入的BinarySearchTree右值引用rhs;
    BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root }
    {
        rhs.root = nullptr;
    }
    
    /// @brief 默认BinarySearchTree析构函数;
    ~BinarySearchTree( )
    {
        makeEmpty( );
    }

    /// @brief 重载=号(赋值)，同时避免了更改rhs的地址;
    /// @param rhs const引用符号右侧的BinarySearchTree类左值对象;
    /// @return 指针this指向的BinarySearchTree对象;
    BinarySearchTree & operator=( const BinarySearchTree & rhs )
    {
        BinarySearchTree copy = rhs;
        std::swap( *this, copy );
        return *this;
    }
        
    /// @brief 重载=号(赋值)，swap函数直接交换地址，因为右值对象马上会被释放;
    /// @param rhs const引用符号右侧的BinarySearchTree类右值对象;
    /// @return 指针this指向的BinarySearchTree对象;
    BinarySearchTree & operator=( BinarySearchTree && rhs )
    {
        std::swap( root, rhs.root );       
        return *this;
    }
    
    /// @brief 找BinarySearchTree类中存储的最小的元素;
    /// @return 若树是空的，直接报错，否则通过调用私有类中findMin函数返回*BinarySearchNode->element，即指针指向的最小元素;
    const Comparable & findMin( ) const
    {
        if( isEmpty( ) )
            throw UnderflowException{ };
        return findMin( root )->element;
    }

    /// @brief 找BinarySearchTree类中存储的最小的元素;
    /// @return 若树是空的，直接报错，否则通过调用私有类中findMax函数返回*BinarySearchNode->element，即指针指向的最大元素;
    const Comparable & findMax( ) const
    {
        if( isEmpty( ) )
            throw UnderflowException{ };
        return findMax( root )->element;
    }

    /// @brief 判断x元素是否在BinarySearchTree中;
    /// @param x 传入的Comparable类型对象的const引用;
    /// @return 通过调用私有类中contains函数，若x元素存在则返回true;否则返回false;
    bool contains( const Comparable & x ) const
    {
        return contains( x, root );
    }

    /// @brief 判断BinarySearchTree是否为空树;
    /// @return 若树非空，返回false，反之返回true;
    bool isEmpty( ) const
    {
        return root == nullptr;
    }

    /// @brief 通过调用私有类中的printList函数，用中序遍历将BinarySearchTree树中元素打印出来;
    /// @param out ostream类对象的一个引用，默认是cout的引用;
    void printTree( ostream & out = cout ) const
    {
        if( isEmpty( ) )
            out << "Empty tree" << endl;
        else
            printTree( root, out );
    }

    /// @brief 通过调用私有类中的makeEmpty函数清空BinarySearchTree; 
    void makeEmpty( )
    {
        makeEmpty( root );
    }

    /// @brief 通过调用私有类中的insert函数将传入的Comparable对象的左值引用x插入到BinarySearchTree中;
    /// @param x 传入的Comparable对象的const左值引用x;
    void insert( const Comparable & x )
    {
        insert( x, root );
    }
     
    /// @brief 通过调用私有类中的insert函数将传入的Comparable对象的右值引用x插入到BinarySearchTree中;
    /// @param x 传入的Comparable对象的const右值引用x;
    void insert( Comparable && x )
    {
        insert( std::move( x ), root );
    }
    
    /// @brief 通过调用私有类中的remove函数将传入的Comparable对象的引用x从BinarySearchTree中移除;
    /// @param x 传入的Comparable对象的const引用x;
    void remove( const Comparable & x )
    {
        remove( x, root );
    }
    /// @brief 通过调用私有类中的add函数将排好序后的元素返回到arr所引用的数组对象;
    /// @param arr 将数据返回到的数组对象arr的引用;
    void add(std::vector<Comparable> &arr) const
    {
        if( isEmpty( ) )
            std::cout << "Empty tree" << std::endl;
        else
            add( root,arr );
    }

  private:
    /// @brief BinaryNode结构体，封装数据;
    struct BinaryNode
    {
        /// @brief BinarySearchTree中的元素值;
        Comparable element;
        /// @brief 指向BinarySearchTree的左子树的指针;
        BinaryNode *left;
        /// @brief 指向BinarySearchTree的右子树的指针;
        BinaryNode *right;
        /// @brief BinarySearchNode列表初始化;
        /// @param theElement 传入的Comparable类型对象的左值引用theElement，作为BinarySearchNode的element成员;
        /// @param lt  传入的BinaryNode指针lt，作为BinarySearchNode的left成员;
        /// @param rt  传入的BinaryNode指针rt，作为BinarySearchNode的right成员;
        BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
          : element{ theElement }, left{ lt }, right{ rt } { }
        /// @brief BinarySearchNode列表初始化;
        /// @param theElement 传入的Comparable类型对象的右值引用theElement，作为BinarySearchNode的element成员;
        /// @param lt 传入的BinaryNode指针lt，作为BinarySearchNode的left成员;
        /// @param rt 传入的BinaryNode指针rt，作为BinarySearchNode的right成员;
        BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt )
          : element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
    };

    /// @brief 指向BinaryNode的指针;
    BinaryNode *root;

    /// @brief BinarySearchTree类的insert函数的内部实现;
    /// @param x 传入的Comparable对象左值引用x（要插入的元素）;
    /// @param t 传入的指向BinaryNode的指针引用t，用于确定当前位置;
    void insert( const Comparable & x, BinaryNode * & t )
    {
        if( t == nullptr )
            t = new BinaryNode{ x, nullptr, nullptr };
        else if( x < t->element )
            insert( x, t->left );
        else if( t->element < x )
            insert( x, t->right );
        else
            ;
    }
    
    /// @brief BinarySearchTree类的insert函数的内部实现;
    /// @param x 传入的Comparable对象右值引用x（要插入的元素）;
    /// @param t 传入的指向BinaryNode的指针引用t，用于确定当前位置;
    void insert( Comparable && x, BinaryNode * & t )
    {
        if( t == nullptr )
            t = new BinaryNode{ std::move( x ), nullptr, nullptr };
        else if( x < t->element )
            insert( std::move( x ), t->left );
        else if( t->element < x )
            insert( std::move( x ), t->right );
        else
            ;
    }

    /// @brief BinarySearchTree类的remove函数的内部实现;
    /// @param x 传入的Comparable对象左值引用x（要删除的元素）;
    /// @param t 传入的指向BinaryNode的指针引用t，用于确定当前位置，保证删除后树的完整性;
    void remove( const Comparable & x, BinaryNode * & t )
    {
        if( t == nullptr )
            return; 
        if( x < t->element )
            remove( x, t->left );
        else if( t->element < x )
            remove( x, t->right );
        else if( t->left != nullptr && t->right != nullptr ) 
        {
            t->element = findMin( t->right )->element;
            remove( t->element, t->right );
        }
        else
        {
            BinaryNode *oldNode = t;
            t = ( t->left != nullptr ) ? t->left : t->right;
            delete oldNode;
      }
    }

    /// @brief BinarySearchTree类的findMin函数的内部实现;
    /// @param t 所寻找的子树以t为根;
    /// @return 返回子树中最小元素所在的节点;
    BinaryNode * findMin( BinaryNode *t ) const
    {
        if( t == nullptr )
            return nullptr;
        if( t->left == nullptr )
            return t;
        return findMin( t->left );
    }

    /// @brief BinarySearchTree类的findMax函数的内部实现;
    /// @param t BinaryNode指针，所寻找的子树以t为根;
    /// @return 返回子树中最大元素所在的节点;
    BinaryNode * findMax( BinaryNode *t ) const
    {
        if( t != nullptr )
            while( t->right != nullptr )
                t = t->right;
        return t;
    }

    /// @brief BinarySearchTree类的contains函数的内部实现;
    /// @param x 传入的Comparable类左值引用（查找的对象）;
    /// @param t BinaryNode指针，所寻找的子树以t为根;
    /// @return 若x在子树中，则返回true，否则返回false;
    bool contains( const Comparable & x, BinaryNode *t ) const
    {
        if( t == nullptr )
            return false;
        else if( x < t->element )
            return contains( x, t->left );
        else if( t->element < x )
            return contains( x, t->right );
        else
            return true;    // Match
    }

    /// @brief BinarySearchTree类的makeEmpty函数的内部实现;
    /// @param t BinaryNode指针引用，需要清空的子树以t为根;
    void makeEmpty( BinaryNode * & t )
    {
        if( t != nullptr )
        {
            makeEmpty( t->left );
            makeEmpty( t->right );
            delete t;
        }
        t = nullptr;
    }

    /// @brief BinarySearchTree类的printTree函数的内部实现;
    /// @param t BinaryNode指针引用，需要打印的子树以t为根;
    /// @param out ostream类对象的一个引用;
    void printTree( BinaryNode *t, ostream & out ) const
    {
        if( t != nullptr )
        {
            printTree( t->left, out );
            out << t->element << endl;
            printTree( t->right, out );
        }
    }

    /// @brief clone函数，用于复制一颗新树;
    /// @param t BinaryNode指针，需要打印的子树以t为根;
    /// @return 复制之后生成的新树;
    BinaryNode * clone( BinaryNode *t ) const
    {
        if( t == nullptr )
            return nullptr;
        else
            return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
    }
    /// @brief 用于将数据返回arr引用的对象中完成排序操作;
    /// @param t 传入的BinarySearchNode对象，递归返回数据;
    /// @param arr 数据返回到的数组对象的引用;
    void add(BinaryNode *t ,std::vector<Comparable> &arr) const
    {
        if(t != nullptr )
        {
            add( t->left,arr );
            arr.push_back(t->element);
            add( t->right,arr );
        }
    }
};
#endif